package com.example.demo.manhua;

/**
 * @ClassName : GCDPlus
 * @Description : 利用移位升级更相减损术
 * * 众所周知，移位运算的性能非常好。对于给出的正整数a和b，不难得到如下的结论。
 * * （从下文开始，获得最大公约数的方法getGreatestCommonDivisor被简写为gcd。）
 * * 当a和b均为偶数时，gcd(a,b) = 2×gcd(a/2, b/2) = 2×gcd(a>>1,b>>1)。
 * * 当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)。
 * * 当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)。
 * * 当a和b均为奇数时，先利用更相减损术运算一次，gcd(a,b) = gcd(b,a-b)，此时a-b
 * * 必然是偶数，然后又可以继续进行移位运算。
 * * 例如计算10和25的最大公约数的步骤如下。
 * * 1. 整数10通过移位，可以转换成求5和25的最大公约数。
 * * 2. 利用更相减损术，计算出25-5=20，转换成求5和20的最大公约数。
 * * 3. 整数20通过移位，可以转换成求5和10的最大公约数。
 * * 4. 整数10通过移位，可以转换成求5和5的最大公约数。
 * * 5. 利用更相减损术，因为两数相等，所以最大公约数是5。
 * * 这种方式在两数都比较小时，可能看不出计算次数的优势；当两数越大时，计算次数
 * * 的减少就会越明显。
 * @Author : wind
 * @Date: 2021-01-27 16:37
 * @Version 1.0
 */
public class GreatestCommonDivisorV3 {

    public static void main(String[] args) {
        System.out.println(gcd(100000000, 1));
        System.out.println(7 & 1);
        System.out.println(8 & 1);
    }

    static int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        // 奇数&1==1 偶数&1==0
        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return gcd(big - small, small);
        }
    }
}
